#include <stddef.h>
#include <stdlib.h>
#include <errno.h>
#include <assert.h>
#include "hmm.h"

/* 实现说明
使用场合：
    1. 小内存块的频繁申请/释放 （小于等于4096）
    2. 不要求提供realloc操作
    3. 不要去单个hmm对象线程安全

细节：
    1. 为小块内存实现了内存池：按大小为8的倍数递增，划分成1024个池，最合一个池为大于4096的内存块服务
    2. 不支持合并操作：多个小块内存合并成大块内存
    3. 每个内存块都会附加一个cookie，大小为4字节，用来保存长度
    4. 释放内存时，按池的原则，在数据区域作一个指针，加入到free单链表中。下次再申请相同大小的内存时，
        直接从链表中摘除
    5. 管理内存的代价：
        a）完成hmm的初始化后，自身会占用内存4104个字节；
        b）每个内存块都附加4字节的cookie
        c）每块内存都做了8字节对齐，意味着如果哪些不是8字节对齐的申请，都会有小于8字节的浪费 
            （对齐是为了在单链表中快速查找，不需要一个个遍历节点的大小）
        d）当自身索引区域没有空间，从下一个索引区域查找有效空间时，会造成空间的浪费。 （也可以考虑对此进行优化）
        e）最后一个内存池节点，存放所有大于4096的内存块。当释放后再分配时，目前是直接找到合适的块，没有对合适进行优化。
                 如1024＊1024可能会因为4097的需求而分配
    6. 获取内存的方式——hmm_malloc的实现：
        a）调用 __malloc进行分配，即从外部源索取
        b）从上次归还的区域（与自己的索引一致）取
        c）当前索引的归还区域没有，从下一个索引的归还区域查找。找到后，必然造成空间的浪费

未实现的扩展：
    1. 如果满足以下要求
        a. 申请内存的大小相对固定，即只有几种大小的申请
        b. free操作要求提供size，既free(void* ptr, int size)
    2. 就可以做优化，能省掉每个内存块的cookie，还能减小hmm_hdr头部大小

*/

/* ALIGN() is only to be used to align on a power of 2 boundary */
#define ALIGN(size, boundary)     (((size) + ((boundary) - 1)) & ~((boundary) - 1))

/** Default alignment */
#define ALIGN_DEFAULT(size) ALIGN(size, 8)

typedef struct block
{
    uint32_t size;
    union
    {
        int32_t next;
        char ptr[sizeof(int32_t)];
    }data;
}block_t;
#define BLOCK_SIZE offsetof(block_t, data)   //must be 4 bytes

#define FREE_BLOCKS_SIZE 1024   //size of free block's array

/*
 block arr's min elem is 8, because sizeof(block_t)=8

int32_t BLOCK_ARR[BLOCKS_SIZE] = 
{
      8,  16,  24,   32,   40,   48,   56, 64, // += 8
    128, 256, 512, 1024, 2048, 4096, 8192, -1  // *= 2
};
 */

typedef struct hmm_hdr
{
    uint32_t size;
    uint32_t used;

    //uint32_t alloc_count;
    //uint32_t free_count;
    //int32_t first; //remember first alloc's offset
    int32_t free_arr[FREE_BLOCKS_SIZE];
}hmm_hdr_t;
#define HMM_HDR_SIZE ALIGN_DEFAULT(sizeof(hmm_hdr_t))

struct hmm
{
    hmm_hdr_t* hdr;
    int (*resize)(void* ctx, uint32_t newsize);
    void* resize_ctx;
};

#define HMM_PTR(off)  ((off)<0)  ? 0 : (void*)((char*)me->hdr + off)
#define HMM_OFF(ptr)  ((ptr)==0) ? HMM_BADOFF : ((char*)(ptr) - (char*)me->hdr)

hmm_t* hmm_new(void* base, uint32_t size)
{
    int i = 0;
    hmm_t* me = malloc(sizeof(*me));

    assert(base && size>HMM_HDR_SIZE);
    if (!me)
        return 0;
    me->hdr = base;
    me->resize = 0;
    me->resize_ctx = 0;

    //init hdr
    me->hdr->size = size;
    me->hdr->used = HMM_HDR_SIZE;
    for (; i<FREE_BLOCKS_SIZE; i++)
    {
        me->hdr->free_arr[i] = HMM_BADOFF;
    }

    return me;
}

hmm_t* hmm_attach(void* base)
{
    hmm_t* me = malloc(sizeof(*me));
    if (!me)
        return 0;
    me->hdr = base;
    me->resize = 0;
    me->resize_ctx = 0;

    //verify hdr
    assert(me->hdr->used >= HMM_HDR_SIZE);
    assert(me->hdr->size > me->hdr->used); 

    return me;
}

void hmm_delete(hmm_t* me)
{
    assert(me);
    free(me);
}

void hmm_detach(hmm_t* me)
{
    assert(me);
    free(me);
}

void hmm_enable_resize(hmm_t* me, int (*resize)(void* ctx, uint32_t newsize), void* ctx)
{
    me->resize = resize;
    me->resize_ctx = ctx;
}

static inline void* __malloc(hmm_t* me, uint32_t size)
{
    uint32_t start = me->hdr->used;
    if ((me->hdr->used + size) > me->hdr->size)
    {
        if (me->resize)
        {
            me->hdr->size += ALIGN(size, 4096);
            if (0 == me->resize(me->resize_ctx, me->hdr->size))
            {
                me->hdr->used += size;
                return HMM_PTR(start);
            }
            return 0;            
        }
        else
        {
            return 0;
        }
    }
    else
    {
        me->hdr->used += size;
        return HMM_PTR(start);
    }
}

static void* hmm_find_valid(hmm_t* me, int32_t idx, uint32_t size)
{
    int32_t i = 0;
    block_t* block = 0;
    if (idx > FREE_BLOCKS_SIZE - 1)
        return 0;
    for (i=idx; i<FREE_BLOCKS_SIZE; i++)
    {
        block = (block_t*)HMM_PTR(me->hdr->free_arr[idx]);
        while(block && block->size < size)
        {
            block = (block_t*)HMM_PTR(block->data.next);
        }

        if (block)
        {
            return block->data.ptr;
        }
    }
    return 0;
}

void* hmm_malloc(hmm_t* me, uint32_t size)
{
    int32_t idx = 0;
    block_t* block = 0;

    size = ALIGN_DEFAULT(size + BLOCK_SIZE);
    idx = size / 8 - 1;
    //more than (FREE_BLOCKS_SIZE - 1), adjust (FREE_BLOCKS_SIZE - 1)
    if (idx > FREE_BLOCKS_SIZE - 1)
        idx = FREE_BLOCKS_SIZE - 1;

    if (me->hdr->free_arr[idx] == HMM_BADOFF)
    {
        block = __malloc(me, size);
        if (block == 0)
        {
            block = hmm_find_valid(me, idx+1, size);
            if (block == 0)
            {
                errno = ENOMEM;
                return 0;
            }
            return block->data.ptr;
        }

        //init
        block->size = size;
        return block->data.ptr;
    }

    block = (block_t*)HMM_PTR(me->hdr->free_arr[idx]);
    if (idx != FREE_BLOCKS_SIZE - 1)
    {
        me->hdr->free_arr[idx] = block->data.next;
    }
    else//the end position
    {
        //find the valid block
        block = hmm_find_valid(me, idx, size);
        if (block == 0)
        {
            block = __malloc(me, size);
            if (block == 0)
            {
                errno = ENOMEM;
                return 0;
            }

            //init
            block->size = size;
            return block->data.ptr;
        }
    }
    return block->data.ptr;
}

void hmm_free(hmm_t* me, void* ptr)
{
    int32_t idx = HMM_BADOFF;
    block_t* block = 0;
    
    assert(me && ptr);
    if (!me || !ptr)
        return ;
    //verify ptr
    assert((char*)ptr >= (char*)hmm_first_ptr(me));
    block = (block_t*)((char*)ptr - BLOCK_SIZE);

    //verify block
    assert(block->size > BLOCK_SIZE);
    assert(block->size % 8 == 0);

    idx = block->size / 8 - 1;
    //more than (FREE_BLOCKS_SIZE - 1), adjust (FREE_BLOCKS_SIZE - 1)
    if (idx > FREE_BLOCKS_SIZE - 1)
        idx = FREE_BLOCKS_SIZE - 1;

    //add to free_arr
    block->data.next = me->hdr->free_arr[idx];
    me->hdr->free_arr[idx] = HMM_OFF(block);
}

int32_t hmm_malloc_off(hmm_t* me, uint32_t size)
{
    void* ptr = hmm_malloc(me, size);
    return ptr? HMM_OFF(ptr) : HMM_BADOFF;
}

void hmm_free_off(hmm_t* me, int32_t off)
{
    assert(me && off >= HMM_HDR_SIZE);
    hmm_free(me, HMM_PTR(off));
}

void* hmm_ptr(hmm_t* me, int32_t off)
{
    assert(me);
    if (off < 0)
    {
        return 0;
    }
    else
    {
        //verify off
        assert(off >= HMM_HDR_SIZE);
        return HMM_PTR(off);
    }
}

int32_t hmm_off(hmm_t* me, void* ptr)
{
    assert(me);
    if (ptr)
    {
        //verify ptr
        assert((char*)ptr >= (char*)hmm_first_ptr(me));
        return HMM_OFF(ptr);
    }
    else
    {
        return HMM_BADOFF;
    }
}

void* hmm_first_ptr(hmm_t* me)
{
    block_t* block = 0;
    assert(me);
    block = (block_t*)HMM_PTR(HMM_HDR_SIZE);
    return block->data.ptr;
}

void hmm_dump(hmm_t* me, FILE* to)
{
    int i = 0;
    hmm_hdr_t* hdr = 0;

    assert(me && to);    
    fprintf(to, "<!--hmm dump start\n");

    //1. header info
    hdr = me->hdr;
    fprintf(to, "hmm size=%d(%.2fk, %.2fm) used=%d(%.2fk, %.2fm) used_rate=%.2f%%\n", hdr->size, (float)hdr->size/1024, (float)hdr->size/1024/1024,
        hdr->used, (float)hdr->used/1024, (float)hdr->used/1024/1024, (float)hdr->used/(float)hdr->size*100);
    fprintf(to, "hmm hdr_size=%d block_size=%d\n", HMM_HDR_SIZE, BLOCK_SIZE);

    //2. free_arr info
    fprintf(to, "free array info: (index, count)\n");
    for (i=0; i<FREE_BLOCKS_SIZE; i++)
    {
        int count = 0;
        block_t* block = hmm_ptr(me, hdr->free_arr[i]);
        while(block)
        {
            count++;
            block = hmm_ptr(me, block->data.next);
        }
        if (count)
            fprintf(to, "(%d, %d)\t", i, count);
    }
    fprintf(to, "\n");

    fprintf(to, "-->\n\n");
}
